COMP2111
System Modelling and Design
Term 1, 2024

Tute (Week 7)

Table of Contents

1 Transition systems

1.1 Question 1

There are 102 coins on a table: 98 showing heads and 4 showing tails. You can do one of two actions:

  • Flip over any 10 coins
  • If there are \(n\) heads showing, add \(n+1\) coins, all showing tails.
  1. Model this as a transition system, clearly defining the states and transitions.
  2. Show how to get to a state with exactly one tail showing.
  3. Show that you cannot get to a state with exactly one head showing.
  4. Are the properties "you can get to a state with exactly one tail showing" and "you cannot get to a state with exactly one head showing" safety, liveness or reachability properties, respectively?

  1. States are pairs of natural numbers representing the number of heads and number of tails. Transitions are determined by the rules, e.g. \((98,4)\to (92,10)\) (flipping 8 heads and 2 tails).

    Formally, the states are \(\mathbb{N} \times \mathbb{N}\) and there is a transition from \((h,t)\) to \((h',t')\) iff either:

    • \(h' = h+10-2m\) and \(t'=t-10+2m\) for some \(m \in [0,10]\) (flip \(m\) heads and \(10-m\) tails), or
    • \(h'=h\) and \(t' = t+h+1\) (add \(h+1\) tails)
  2. \((98,4)\to (88,14) \to (78,24) \to \cdots \to (8,94) \to (8,103) \to (10,101) \to (20,91) \to \cdots (110,1)\) where \((8,103)\to(10,101)\) is obtained by flipping 4 heads and 6 tails.
  3. The parity of the number of heads is a preserved invariant. So \((1,x)\) is not reachable from \((98,4)\).
  4. "You can get to a state with exactly one tail showing" is a reachability property. "You cannot get to a state with exactly one head showing" is a safety property.

2 Automata

2.1 Question 1

Let \(\Sigma = \{0, 1\}\). Give DFAs over \(\Sigma\) that accept the following languages:

  1. All words except the empty word.
  2. All words containing at least two 0s and at most one 1.
  3. All words containing contains an even number of 0s, or exactly two 1s.

With 2 and 3 the best approach is to consider what information needs to be ``stored'' – this is the information we keep in the states of the DFA.

  1. tute7_sol11.png
  2. You can think of the "x axis" as representing the number of 0s, and the "y axis" as representing the number of 1s. tute7_sol21.png
  3. You can think of the "x axis" as representing the number of 1s, and the "y axis" as representing the parity of the 0s. tute7_sol31.png

2.2 Question 2

Consider the following DFA:

tute7_dfa.png

  1. Describe the language accepted by the automaton
  2. Give an NFA with 4 states that accepts the same language
  1. The set of all words that start and end with the same symbol.
  2. tute7_sol41.png

2.3 Question 3

Are regular languages closed under word reversal? That is, if \(L\) is a regular language and \(L'\) is the language obtained by reversing all the words in \(L\), is \(L'\) regular?

Yes. Take a DFA for \(L\). Reverse all the transitions (note this will necessarily make it an NFA). Add a new start state with \(\epsilon\) transitions to all the final states of the original automaton. Set the new final state to be the original start state. The language accepted by this NFA will be \(L'\).

2.4 Question 4

Give regular expressions for each of the following subsets of \(\{a, b\}^\ast\).

  1. All words that contain an even number of \(a\) symbols.
  2. All words that contain an odd number of \(b\) symbols.
  3. All words containing an even number of \(a\) symbols or an odd number of \(b\) symbols.
  1. E.g. \(b^{\ast}(ab^{\ast}ab^{\ast})^{\ast}\) or \((b + ab^{\ast}a)^{\ast}\)
  2. E.g. \((a^{\ast}ba^{\ast}b )^{\ast}(a^{\ast}ba^{\ast})\) or \(a^{\ast}b(a + ba^{\ast}b)^{\ast}\)
  3. Use union (\(+\)) to combine (a) and (b).

2024-04-19 Fri 10:38

Announcements RSS